﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<vector>
#include<unordered_map>
#include<thread>
#include<assert.h>
#include<mutex>
#include<algorithm>



static const size_t MAX_BYTES = 256 * 1024;//哈希表的大小
static const size_t NFREELIST = 208;//桶的数量
static const size_t NPAGES = 129; 
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN32
#include<windows.h>
#else
//
#endif

//页的数量跟系统操作位数有关
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif


//直接去堆上申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT),
		MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

#else
	//linux下brk mmap等
#endif


	if (ptr == nullptr)
	{
		throw std::bad_alloc();
	}
	return ptr;
}


//释放空间到堆
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	//sbrk unmmap等
#endif // _WIN32;

}


//获得自由链表节点的下一个节点
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//管理切分好的小对 象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{	
		//头插
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	//范围头插
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}

	//范围删除
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}

		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	void* Pop()
	{
		//头删
		assert(_freeList);
		void* obj = _freeList;
		_freeList = NextObj(obj);
		_size--;
		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList=nullptr;
	size_t _maxSize = 1;
	size_t _size=0;
};

//计算对象大小的对其规则
class SizeClass
{
	//分段内存对齐
	// 整体控制在最多10%左右的内碎片浪费
    // [1,128] 8byte对齐       freelist[0,16)
    // [128+1,1024] 16byte对齐   freelist[16,72)
    // [1024+1,8*1024] 128byte对齐   freelist[72,128)
    // [8*1024+1,64*1024] 1024byte对齐     freelist[128,184)
    // [64*1024+1,256*1024] 8*1024byte对齐   freelist[184,208)

	/*size_t _RountUp(size_t size,size_t alignNum)
	{
		size_t alignSize;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1) * alignNum; 
		}
		else {
			alignSize = size;
		}
	}*/
public:
	static inline size_t _RountUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));//获得的一定是一个>=alignNum且是alignNum的倍数
	}

	static inline  size_t RountUp(size_t size)
	{
		if (size <= 128)
		{
			return _RountUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RountUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RountUp(size, 128);
		}
		else if (size<=64 * 1024)
		{
			return _RountUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RountUp(size, 8 * 1024);
		}
		else
		{
			return _RountUp(size, 1 << PAGE_SHIFT);
		}
	}
	//thread cache一次从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		if (size == 0)return 0;

		//[2,512],一次批量移动多少个对象的（慢启动）上限值
		//小对象给多点
		//大对象给少点
		int num = MAX_BYTES / size;
		if (num < 2)//控制下限
		{
			num = 2;
		}
		if (num > 512)//控制上限 
		{
			num = 512;
		}
		return num;
	}

	//计算central cache一次向系统获取几个页
	//单个对象 8byte
	//...
	//单个对象 256kb
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);//小对象的数量
		size_t npage = num * size;//字节数
		npage >>= PAGE_SHIFT;//除以8KB，计算有多少页
		if (npage == 0)//不够补一
			npage = 1;
		return npage;
	}
	
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;//(bytes/align_shift) 向上取整再-1
	}
	//定位自由链表桶在哈希表的位置
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		//每个区间有多少个链
		static int group_array[4] = { 16,56,56,56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];//还要加上前面不同对齐数桶的偏移量
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[0]+group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 1024*8, 10) + group_array[0] + group_array[1]+group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 1024 * 64, 13) + group_array[0] + group_array[1] + group_array[2]+group_array[3];
		}
		else {
			assert(false);
		}
		return 0;
	}

};

//管理多个连续页大块内存内存跨度结构
struct Span
{
	PAGE_ID _pageId=0;//大块内存起始页的页号
	size_t _n=0;//页的数量

	Span* _next=nullptr;//双向链表的结构
	Span* _prev=nullptr;
	
	size_t _objSize = 0;//切好的小对象的大小 ，同一个span内的小对象大小是一样的
	size_t _useCount=0;//切好的小块内存，被分配给thread cache的计数， 表示有多少个小块内存被使用
	void* _freeList=nullptr;//切好的小块内存的自由链表

	bool _isUse;//是否在被使用，防止page cache合并了正在使用的span
};

//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(Span* pos,Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;

		newSpan->_next = pos;
		newSpan->_prev = prev;

		pos->_prev = newSpan;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* Begin()
	{
		return _head->_next;
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	Span* End()
	{
		return _head;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
private:
	Span* _head;
public:
	std::mutex _mtx;//桶锁
};